1249. Minimum Remove to Make Valid Parentheses

Question

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string.

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Constraints:

- 1 <= s.length <= 105
- s[i] is either'(' , ')', or lowercase English letter.

---

Approach

1. Iterate through the string and identify '(', keep track of the index of this element.
2. If ')' is found but stack is empty, that means it is not valid i.e. closed without opening, mark this element as ?. Otherwise pop the top of the stack and consider this pair of parentheses are ok.
3. After which, if the stack is not empty, that means there are some invalid parentheses. Identify these and mark as ? as well. Pop till the stack is empty.
4. Check the final string, as long as it is not invalid (?), return the result.

Solution

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        string out;
        stack<int> par;
        
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '('){
                par.push(i);
            }else if(s[i] == ')'){
                if(par.empty()) s[i] = '?';
                else par.pop();
            }
    
        }
        
        while(!par.empty()){
            s[par.top()] = '?';
            par.pop();
        }
        
        for(int i = 0; i < s.size(); i++){
            if(s[i] != '?') out.push_back(s[i]);
        }
        
        return out;
    }
};